#include <stdio.h>
int count,n,k,a[9][2];
void dfs(int score,int t)
{
    if (t<=k-1)
    {
        for (int i=0;i<=a[t][1];i++)
        {
            if (i*a[t][0]+score>n)break;
            if (i*a[t][0]+score==n)count++;
            if (i*a[t][0]+score<n)dfs(score+i*a[t][0],t+1);
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int i;
        scanf("%d%d",&n,&k);
        for (i=0;i<k;i++)
            scanf("%d%d",&a[i][0],&a[i][1]);
        count=0;
        dfs(0,0);
        printf("%d\n",count);
    }
    return 0;
}